#include <cstdlib>
#include <fstream>
#include <string>
#include <queue>
#include <stack>
using namespace std;

template <class ItemType>
class BinaryTree;

template <class ItemType>
class NodeType;

template <class ItemType>
class NodeType
{
	friend class BinaryTree<ItemType>;

public:
	NodeType();
	NodeType(const ItemType &value);

private:
	ItemType info;
	NodeType<ItemType> *left;
	NodeType<ItemType> *right;
};

template <class ItemType>
NodeType<ItemType>::NodeType()
{
	left = NULL;
	right = NULL;
}

template <class ItemType>
NodeType<ItemType>::NodeType(const ItemType &value)
{
	info = value;
	right = NULL;
	left = NULL;
}

template <class ItemType>
class BinaryTree   
{
public:

    BinaryTree();		
    //default constructor

	~BinaryTree();
	//deconstructor

    BinaryTree(const BinaryTree &orig);		
    //copy constructor

    BinaryTree operator=(const BinaryTree<ItemType>& rhs);
    //assignment operator

    void PrintPre(ostream &out);
    //Pre:  none.
    //Post: prints tree using preorder traversal.

    void Insert(ItemType value, string trail);
    //Pre:  none.
    //Post: inserts a new node in tree

    bool DeleteSubtreeAt(ItemType value);
    //Pre:  none.
    //Post: if item is found the entire subtree
	//      is deleted from the tree

	bool SiblingOf(ItemType val, ItemType &sibling);
    //Pre:  none.
    //Post: if item is found and has a sibling
	//      the sibling's value is returned as well as true

	void PrintBottomToTop(ostream& out);
	//Pre:  none.
    //Post: prints the tree from the bottom up

	bool InOrderNext(ItemType value, ItemType& next);
	//Pre:  none.
    //Post: returns true if next item is found, next item is also returned

	ItemType RightmostOnLevel(int level);
	//Pre:  none.
    //Post: returns the right most item on the specified level

	double AvgLeafDepth();
	//Pre:  none.
    //Post: calculates the average leaf depth of tree

private:

	NodeType<ItemType>* root;

	void clearTree(NodeType<ItemType>* tree);
	void copyTree(const BinaryTree<ItemType>& orig);
	void copy2(NodeType<ItemType>*& current, NodeType<ItemType>* sourceCurrent);
	void Insert2(ItemType value, string trail, NodeType<ItemType> *tree);
	void PrintPre2(ostream& out, NodeType<ItemType>* current);
	bool deleteSubTreeAt2(ItemType value, NodeType<ItemType>* current);
	bool SiblingOf2(ItemType value, ItemType& sibling, NodeType<ItemType>* current);
	bool inOrder2(ItemType value, ItemType& next, NodeType<ItemType>* current, bool& itemFound);
	void RightmostOnLevel2(queue<NodeType<ItemType>*>& Q, int level, NodeType<ItemType>* current, int thisLevel);
	void findLeaves(queue<int>& Q, NodeType<ItemType>* current, int level);

};

#include "tree.cpp"